首页 > 试题广场 >

二叉搜索树与双向链表

[编程题]二叉搜索树与双向链表

热度指数：626299 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示

数据范围：输入二叉树的节点数 $0 \le n \le 1000$ ，二叉树中每个节点的值 $0\le val \le 1000$
要求：空间复杂度 $O(1)$ （即在原树上操作），时间复杂度 $O(n)$

注意:

1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
2.返回链表中的第一个节点的指针
3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构

4.你不用输出双向链表，程序会根据你的返回值自动打印输出

输入描述:

二叉树的根节点

输出描述:

双向链表的其中一个头节点。

示例1

输入

{10,6,14,4,8,12,16}

输出

From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4;

说明

输入题面图中二叉树，输出的时候将双向链表的头节点返回即可。

示例2

输入

{5,4,#,3,#,2,#,1}

输出

From left to right are:1,2,3,4,5;From right to left are:5,4,3,2,1;

说明

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

推荐

nailperry

方法一：非递归版
解题思路：
1.核心是中序遍历的非递归算法。
2.修改当前遍历节点与前一遍历节点的指针指向。
    import java.util.Stack;
    public TreeNode ConvertBSTToBiList(TreeNode root) {
    	if(root==null)
    		return null;
    	Stack<TreeNode> stack = new Stack<TreeNode>();
    	TreeNode p = root;
    	TreeNode pre = null;// 用于保存中序遍历序列的上一节点
    	boolean isFirst = true;
    	while(p!=null||!stack.isEmpty()){
    		while(p!=null){
    			stack.push(p);
    			p = p.left;
    		}
    		p = stack.pop();
    		if(isFirst){
    			root = p;// 将中序遍历序列中的第一个节点记为root
    			pre = root;
    			isFirst = false;
    		}else{
    			pre.right = p;
    			p.left = pre;
    			pre = p;
    		}		
    		p = p.right;
    	}
    	return root;
    }
方法二：递归版
解题思路：
1.将左子树构造成双链表，并返回链表头节点。
2.定位至左子树双链表最后一个节点。
3.如果左子树链表不为空的话，将当前root追加到左子树链表。
4.将右子树构造成双链表，并返回链表头节点。
5.如果右子树链表不为空的话，将该链表追加到root节点之后。
6.根据左子树链表是否为空确定返回的节点。
    public TreeNode Convert(TreeNode root) {
    	if(root==null)
    		return null;
    	if(root.left==null&&root.right==null)
    		return root;
    	// 1.将左子树构造成双链表，并返回链表头节点
    	TreeNode left = Convert(root.left);
    	TreeNode p = left;
    	// 2.定位至左子树双链表最后一个节点
    	while(p!=null&&p.right!=null){
    		p = p.right;
    	}
    	// 3.如果左子树链表不为空的话，将当前root追加到左子树链表
    	if(left!=null){
    		p.right = root;
    		root.left = p;
    	}
    	// 4.将右子树构造成双链表，并返回链表头节点
    	TreeNode right = Convert(root.right);
    	// 5.如果右子树链表不为空的话，将该链表追加到root节点之后
    	if(right!=null){
    		right.left = root;
    		root.right = right;
    	}
		return left!=null?left:root;        
    }
方法三：改进递归版
解题思路：
思路与方法二中的递归版一致，仅对第2点中的定位作了修改，新增一个全局变量记录左子树的最后一个节点。
    // 记录子树链表的最后一个节点，终结点只可能为只含左子树的非叶节点与叶节点
    protected TreeNode leftLast = null;
    public TreeNode Convert(TreeNode root) {
    	if(root==null)
    		return null;
    	if(root.left==null&&root.right==null){
    		leftLast = root;// 最后的一个节点可能为最右侧的叶节点
    		return root;
    	}
    	// 1.将左子树构造成双链表，并返回链表头节点
    	TreeNode left = Convert(root.left);
    	// 3.如果左子树链表不为空的话，将当前root追加到左子树链表
    	if(left!=null){
    		leftLast.right = root;
    		root.left = leftLast;
    	}
    	leftLast = root;// 当根节点只含左子树时，则该根节点为最后一个节点
    	// 4.将右子树构造成双链表，并返回链表头节点
    	TreeNode right = Convert(root.right);
    	// 5.如果右子树链表不为空的话，将该链表追加到root节点之后
    	if(right!=null){
    		right.left = root;
    		root.right = right;
    	}
		return left!=null?left:root;        
    }

编辑于 2015-08-18 23:36:07 回复(111)

Python 3

JianYue

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

#
# 
# @param pRootOfTree TreeNode类 
# @return TreeNode类
#
class Solution:
    def Convert(self , pRootOfTree ):
        if pRootOfTree is None:
            return None
        ret = pRootOfTree
        right = self.Convert(pRootOfTree.right)
        if right:
            right.left = pRootOfTree
            pRootOfTree.right = right
        left = self.Convert(pRootOfTree.left)
        if left:
            ret = left
            while left.right:
                left = left.right
            left.right = pRootOfTree
            pRootOfTree.left = left
        return ret

发表于 2022-09-16 14:48:18 回复(0)

Python 3

小大小菜鸡

非递归中序遍历解法

class Solution:
    def Convert(self , root):
        if not root:
            return
        dummy = TreeNode(0)
        cur = dummy
        s = []
        while root&nbs***bsp;s:
            while root:
                s.append(root)
                root = root.left
            n = s.pop()
            root = n.right
            cur.right = n
            n.left = cur
            cur = n
        dummy.right.left = None
        return dummy.right

发表于 2022-07-20 11:51:59 回复(0)

Python 3

YiMo_以沫

若当前节点为空返回，否则先遍历左子树找到最小的值，并且每次遍历保存当前节点的前一个节点，然后左子树遍历完了之后，与当前的根节点互指，再遍历右子树。注意保存头节点。

class Solution:
    def Convert(self , pRootOfTree ):
        # write code here
        def dfs(cur):
            if not cur: return
            dfs(cur.left)
            if self.pre:
                self.pre.right, cur.left = cur, self.pre
            else:
                self.head = cur
            self.pre = cur
            dfs(cur.right)
        
        if not pRootOfTree: return None
        self.pre, self.head = None, None
        dfs(pRootOfTree)
        return self.head

发表于 2022-06-20 21:39:05 回复(0)

Python 3

Vivimore

中序遍历 + 创建pre保存前一个节点，树左右指针代表链表前后指针

class Solution:
    res = None
    pre = None
    def Convert(self , root ):
        if not root:
            return
        self.Convert(root.left)
        if not self.res and not self.pre:
            self.res = root
            self.pre = root
        else:
            self.pre.right = root
            root.left = self.pre
            self.pre = root
        self.Convert(root.right)
        return self.res

发表于 2022-06-17 14:33:24 回复(0)

Python 3

牛客729667213号

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

# @param pRootOfTree TreeNode类 
# @return TreeNode类
#
#中序遍历使得节点按照顺序输出， 左子树的尾部和节点连接再和右子树的头部连接，一直递归下去
class Solution:
    def Convert(self , pRootOfTree ):
        # write code here
        root = pRootOfTree
        def in_order(root):
            if root.left and root.right:
                left_head,left_tail = in_order(root.left)
                right_head,right_tail = in_order(root.right)
                left_tail.right = root
                root.right = right_head
                right_head.left = root
                root.left = left_tail
            elif root.left:
                left_head,left_tail = in_order(root.left)
                #right_head,right_tail = in_order(root.right)
                left_tail.right = root
                #root.right = right_head
                #right_head.left = root
                root.left = left_tail
                left_head = left_head
                right_tail = root
            elif root.right:
                #left_head,left_tail = in_order(root.left)
                right_head,right_tail = in_order(root.right)
                #left_tail.right = root
                root.right = right_head
                right_head.left = root
                #root.left = left_tail 
                left_head = root
                right_tail = right_tail
            else:
                left_head = root
                right_tail = root
            return left_head, right_tail
        if not root:
            return root
        else:
            head, tail = in_order(root)
            return head

发表于 2022-04-10 23:17:34 回复(0)

Python 3

牛客703888323号

# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

#
#
# @param pRootOfTree TreeNode类
# @return TreeNode类
#
class Solution:
def bianli(self,pRootOfTree):
# write code here
if pRootOfTree == None:
return None
# 进行单元处理
self.bianli(pRootOfTree.left)
self.nodes.append(pRootOfTree)
self.bianli(pRootOfTree.right)

def Convert(self , pRootOfTree):
if pRootOfTree==None:
return None
self.nodes = []
self.bianli(pRootOfTree)
# 遍历数组
if len(self.nodes)==1:
return self.nodes[0]
for nodei,node in enumerate(range(len(self.nodes))) :
if nodei==0:
self.nodes[nodei].left = None
self.nodes[nodei].right = self.nodes[nodei+1]
elif nodei == len(self.nodes)-1:
self.nodes[nodei].right = None
self.nodes[nodei].left = self.nodes[nodei-1]
else:
self.nodes[nodei].left = self.nodes[nodei-1]
self.nodes[nodei].right = self.nodes[nodei+1]
return self.nodes[0]

发表于 2022-03-27 16:31:32 回复(0)

Python 3

kinter1

class Solution:
    def Convert(self , pRootOfTree ):
        self.pre = None
        def dfs(root, pre):
            if root.left:
                dfs(root.left, self.pre)
            if self.pre is None:
                head.left = root
                root.left = None
            else:
                root.left = self.pre
                self.pre.right = root
            self.pre = root
            if root.right:
                self.pre.right = root.right
                dfs(root.right, self.pre)
        if pRootOfTree is None:
            return None
        head = TreeLinkNode(-1)
        dfs(pRootOfTree, self.pre)
        return head.left

pre指针必须为全局变量

发表于 2022-03-04 15:41:18 回复(0)

Python 3

陈鑫泉

一开始就想到需要用中序遍历, 但是写出来后发现返回值和Convert的不一样, 所以有inOrder肯定也是需要另外写的, 还有一点就是不懂inOrder的返回值, 这时候我犯了一个不应该的错误, 就是从特例找解决方案, 我看别人的方法使用了一个preNode, 很巧妙的利用搜索树中序遍历递增的特性, 只需要对p reNode进行处理, 而此次root的right子节点会被赋值给p reNode, 在下一次被处理. 所以说, python中对指针的使用还是很重要的.

发表于 2022-01-30 16:09:26 回复(0)

Python 3

牛客487200401号

有个疑问：

按照题目要求，中序遍历的结果中，每个节点的左指针需要指向前驱，右指针需要指向后继，那么树中的叶子节点即4，8，12，16没有后继，其右指针不应该有指向啊？

发表于 2022-01-12 13:46:23 回复(1)

Python 3

阿司匹林Yo

class Solution:
    def buildLinked(self, node, front):
        if not node:
            return
        self.buildLinked(node.left, front)
        node.left = front[0]
        if front[0]:
            front[0].right = node
        front[0] = node
        self.buildLinked(node.right, front)

    def Convert(self, pRootOfTree):
        if not pRootOfTree:
            return None
        front = [None]
        self.buildLinked(pRootOfTree, front)
        while pRootOfTree.left:
            pRootOfTree = pRootOfTree.left
        return pRootOfTree

发表于 2021-08-23 01:05:55 回复(0)

Python 3

大霞上仙

# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

#
#
# @param pRootOfTree TreeNode类
# @return TreeNode类
#
class Solution:

def Convert(self , pRootOfTree ): # 返回头
# write code here
if pRootOfTree is None:
return None
temp = self.Convert(pRootOfTree.left) # 头
top = temp
pre = temp
while temp is not None:
pre = temp # 尾
temp = temp.right
nxt = self.Convert(pRootOfTree.right) # 头
if pre is not None:
pRootOfTree.left = pre
pre.right = pRootOfTree
if nxt is not None:
pRootOfTree.right = nxt
nxt.left = pRootOfTree
if pre is not None:
return top
else:
return pRootOfTree

发表于 2021-08-14 16:17:06 回复(0)

Python 3

tantantansq

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

#
# 
# @param pRootOfTree TreeNode类 
# @return TreeNode类
#
class Solution:
    def Convert(self , pRootOfTree ):
        # write code here
        if pRootOfTree==None:
            return None
        p=pRootOfTree
        Stack=[]
        R=[]
        while p!=None&nbs***bsp;len(Stack)>0:
            while p!=None:
                Stack.append(p)
                p=p.left
            p=Stack.pop()
            R.append(p)
            if p.right!=None:
                p=p.right
            else:
                p=None
        
        for i in range(len(R)-1):
            R[i].right=R[i+1]
            R[i+1].left=R[i]
        R[0].left=None
        R[-1].right=None

        
        
        return R[0]

发表于 2021-08-08 16:48:35 回复(0)

Python 3

xxxxw

class Solution:
    def Convert(self , pRootOfTree ):
        # write code here
        if not pRootOfTree:return
        treeList = []
        def mid(root):
            if root.left:
                mid(root.left)
            treeList.append(root)
            if root.right:
                mid(root.right)
        
        mid(pRootOfTree)
        
        for i in range(len(treeList)-1):
            treeList[i].right = treeList[i+1]
            treeList[i+1].left = treeList[i]
        return treeList[0]

编辑于 2021-07-16 15:15:14 回复(0)

提交观点

问题信息

分治

难度：

14条回答 5489收藏 153075浏览

通过挑战的用户

查看代码

牛客39358...

2023-03-13 14:57:19
Elastic...

2023-02-26 14:54:56
随机昵称都有什...

2023-02-20 18:19:11
想笑

2023-02-20 15:17:25
想吃卤蛋的99...

2023-01-09 14:39:12

二叉搜索树与双向链表

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

问题信息

热门推荐

通过挑战的用户

相关试题